/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.sort
 * author:David
 * Date:2015年6月13日下午6:05:22
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.sort;

/**
 * 归并排序
 * @author David
 * @since 2015年6月13日 下午6:05:22
 * @version  
 * @since JDK 1.6
 */
public class MergeSort implements Strategy{

	/**
	 * @param r
	 * @param low
	 * @param high
	 */
	public void mergeSort(int[]arr,int low,int high) {
		if(low<high){
			mergeSort(arr,low,(low+high)/2);
			mergeSort(arr,(low+high)/2+1,high);
			merge(arr,low,(high+low)/2,high);
		}
	
	}

	private void merge(int[]arr,int p,int q,int r){
		int[]b=new int[r-p+1];
		int s=p;
		int t=q+1;
		int k=0;
		while(s<=q&&t<=r){
			if(compare(arr[s],arr[t])<0){
				b[k++]=arr[s++];
			}else{
				b[k++]=arr[t++];
			}
		}
		while(s<=q)b[k++]=arr[s++];
		while(t<=r)b[k++]=arr[t++];
		for(int i=0;i<b.length;i++){
			arr[p+i]=b[i];
		}
	}

	
	@Override
	public boolean equal(int obj1, int obj2) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public int compare(int obj1, int obj2) {
		if(obj1<obj2){
			return -1;
		}else if(obj1==obj2){
			return 0;
		}else{
			return 1;
		}
	}
	
	public static void main(String[] args){
		int[] arr={-1,9,0,5,2,-7};
		System.out.println("排序前：");
		for(int a:arr){
			System.out.print(a+",");
		}
		System.out.print("end");
		new MergeSort().mergeSort(arr, 0, 5);
		System.out.println("\n排序后：");
		for(int a:arr){
			System.out.print(a+",");
		}
		System.out.print("end");
	}
}
